package dp.剑指;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 剑指Offer10青蛙跳台阶问题.java
 * @Description https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 * @createTime 2021年12月11日 13:34:00
 *
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 */
public class 剑指Offer10青蛙跳台阶问题 {
	public int numWays(int n) {
		if (n<2){
			return 1;
		}
		//定义 dp[i]表示 台阶到达台阶i的方法
		int[] dp=new int[n+1];

		//初始化
		dp[0]=1;
		dp[1]=1;

		/**
		 * 台阶i到达的方式 dp[i]=dp[i-1]+dp[i-2]
		 */
		for (int i = 2; i <= n; i++) {
			dp[i]=(dp[i-1]+dp[i-2])%1000000007;
		}
		return dp[n];
	}
}
